1. Field of the Invention
This invention relates to computer systems, and more particularly, to minimizing register spills during compilation.
2. Description of the Relevant Art
The performance of computer systems is dependent on both hardware and software. In addition to advances in hardware design, advances in compiler design attempt to increase system performance by reducing inefficient code execution. During the later stages, or phases, of compilation, compilers typically perform machine-dependent optimizations on intermediate code representations. One such optimization includes techniques for register allocation, wherein machine registers are assigned to the many variables used in the algorithm of the source code. Prior to register allocation, these variables are stored in an unlimited number of temporary registers, wherein these temporary registers may be virtual registers. The machine registers, or physical registers, are the registers used in the one or more register files of the processor. These registers are also referred to as architectural registers. A processor may have at least one integer register file and one floating-point register file. In such a case, an integer register may be assigned an integer variable and a floating-point register may be assigned a floating-point variable.
The register-to-variable assignments may not be set during the entire execution time of the program code. Rather, these assignments may correspond to varying periods of time in which they are valid, or utilized. It may be said that a variable has a “live range”, where a live range may be measured as the range of time between when a first instruction (producer) assigns a value to the variable and when a second instruction (last consumer) last consumes the value of the variable. The producer and consumer instructions correspond to an intermediate representation of the source code, which is used during this phase of machine-dependent compilation. After the second instruction, or the last consumer, the variable may not be used again. Alternatively, the variable may be assigned again by a later third instruction, which would initiate another live range.
The live ranges of variables as described above may be measured by an instruction count or a cycle count. Similarly, a machine register live range may be defined as a period of time the machine register is assigned a variable and the variable is utilized. Therefore, a machine register has periods of time that it is assigned with a value of a variable and utilized, periods of time it is assigned but not utilized, and periods of time it is not assigned. A machine register may be assigned to different variables during different time periods.
The number of machine registers is finite and relatively small compared to the number of variables requiring storage assignment. During the register allocation phase, a stack implemented in memory is assigned to store variables when at a particular period of time the number of variables requiring storage is greater than a number of available machine registers in a corresponding register file. The variables that are not assigned to machine registers are “spilled” to the stack memory. The variables, or spill values, will be reloaded from the stack memory to a machine register before the variables are used. Memory access operations, such as store and load instructions, are used to spill values to the stack memory and to reload spill values from the stack. Therefore, in the intermediate representation of the source code, the virtual registers without a machine register assignment will be spilled to the stack such that a define of the virtual register (producer instruction) will be followed by a store operation to the stack and a use of the virtual register (consumer instruction) will be proceeded by a load operation from the stack.
The disadvantages of spilling values to the stack include memory access operations requiring more time than moving values between registers. Programs typically need many memory accesses, and, therefore, the performance may be limited by the accesses to the stack memory. Also, the demand for a critical resource, such as memory, increases with additional accesses due to register spills. In addition, a reload of a spilled value typically requires more time to perform than a normal load operation since there is often a read-after-write (RAW) penalty when reloading a value that has been recently stored. Further, the store queue may fill with spill values. Consequently, there may be little remaining space for other updates to memory, and this limited space in the store queue may lead to delays in processing store operations.
In view of the above, efficient methods and mechanisms for minimizing register spills during compilation are desired.